package com.zds.leetcode;

import java.util.LinkedList;
import java.util.List;

public class q_95 {

    public static void main(String[] args) {
        // 返回生成所有二叉生成树的结构
        generateTrees(2).forEach(TreeNode::printTreeNode);
    }

    public static List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }

    private static List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获取所有可行的左子树
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            // 获取所有可行的右子树
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            // 从左子树中选出一颗左子树，从右子树集合中选出一颗右子树，拼接到根节点上
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode tmp = new TreeNode(i);
                    tmp.left = leftTree;
                    tmp.right = rightTree;
                    allTrees.add(tmp);
                }
            }

        }
        return allTrees;
    }
}
